package leetcode

import "Algorithms/datastruct"

//851. 喧闹和富有
func loudAndRich(richer [][]int, quiet []int) []int {
	n := len(quiet)
	g := make([][]int, n)
	res := make([]int, n)
	//初始化图和返回切片
	for i := 0; i < n; i++ {
		res[i] = -1
	}
	for i := 0; i < len(richer); i++ {
		g[richer[i][1]] = append(g[richer[i][1]], richer[i][0])
	}
	//深度遍历
	var dfs func(x int)
	dfs = func(x int) {
		if res[x] != -1 {
			return
		}
		res[x] = x
		for _, y := range g[x] {
			dfs(y)
			if quiet[res[y]] < quiet[res[x]] {
				res[x] = res[y]
			}
		}
	}
	for i := 0; i < n; i++ {
		dfs(i)
	}
	return res
}

//解法2，拓扑排序
func loudAndRich2(richer [][]int, quiet []int) []int {
	n := len(quiet)
	g := make([][]int, n)
	res := make([]int, n)
	//入度
	inDeg := make([]int, n)

	for i := 0; i < n; i++ {
		res[i] = i
	}
	for i := 0; i < len(richer); i++ {
		g[richer[i][0]] = append(g[richer[i][0]], richer[i][1])
		inDeg[richer[i][1]]++
	}

	q := datastruct.Queue{
		Head: nil,
		Tail: nil,
	}
	for i, v := range inDeg {
		if v == 0 {
			q.Enqueue(i)
		}
	}
	for !q.IsEmpty() {
		x := q.Dequeue().(int)
		for _, y := range g[x] {
			if quiet[res[x]] < quiet[res[y]] {
				res[y] = res[x]
			}
			//x遍历过了就减少一个y的入度
			inDeg[y]--
			if inDeg[y] == 0 {
				q.Enqueue(y)
			}
		}
	}
	return res
}

//200. 岛屿数量，先找到陆地，然后广度遍历，标记visited，然后再继续找陆地
func numIslands(grid [][]byte) int {
	m, n := len(grid), len(grid[0])
	visited := make([][]bool, m)
	for i := range visited {
		visited[i] = make([]bool, n)
	}
	var dfs func(i, j int)
	dfs = func(i, j int) {
		if i < 0 || i >= m || j < 0 || j >= n {
			return
		}
		if grid[i][j] != '1' {
			return
		}
		if visited[i][j] {
			return
		}
		visited[i][j] = true
		dfs(i-1, j)
		dfs(i+1, j)
		dfs(i, j-1)
		dfs(i, j+1)
	}
	ans := 0
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			if !visited[i][j] && grid[i][j] == '1' {
				//广度遍历
				dfs(i, j)
				ans++
			}
		}
	}
	return ans
}

//207. 课程表
func canFinish(numCourses int, prerequisites [][]int) bool {
	m := make(map[int][]int)
	for i := range prerequisites {
		if _, ok := m[prerequisites[i][0]]; !ok {
			m[prerequisites[i][0]] = []int{}
		}
		m[prerequisites[i][0]] = append(m[prerequisites[i][0]], prerequisites[i][1])
	}
	visited := make([]bool, numCourses)
	dp:=make([]bool,numCourses)
	found := false
	var dfs func(int)
	dfs = func(i int)   {
		if found||dp[i] {
			return
		}
		if v,ok:=m[i];!ok||len(v)==0{
			dp[i]=true
			return
		}else {
			for j:=range v{
				if visited[v[j]]{
					found=true
					return
				}
				visited[v[j]]=true
				dfs(v[j])
				visited[v[j]]=false
				dp[v[j]]=true
			}
		}
	}
	for k, v := range m {
		for j:=range v{
			visited[k]=true
			dfs(v[j])
			visited[k]=false
			dp[k]=true
		}
	}
	return !found
}
